20.8 KB · ⇊ 7 parts · ⤓ Micron 20.8 KB · ⤓ HTML 66.9 KB

top

In mwawmatematica, un mwbasemigruppo è un mwbqinsieme munito di un'mwbgoperazione binaria mwbwassociativa. In altre parole per semigruppo si intende una mwcastruttura algebrica espressa da una coppia mwcq ( A , ∗ ∗ ) {\displaystyle (A,*)} con mwcg A {\displaystyle A} insieme e mwcw ∗ ∗ {\displaystyle *} funzione definita su mwda A × × A {\displaystyle A\times A} a valori in mwdq A {\displaystyle A} per la quale si ha:

mwea a ∗ ∗ ( b ∗ ∗ c ) = ( a ∗ ∗ b ) ∗ ∗ c per ogni a , b , c ∈ ∈ A . {\displaystyle a*(b*c)=(a*b)*c\qquad {\text{per ogni }}a,b,c\in A.}

Equivalentemente si può definire come semigruppo ogni mwegmagma associativo.

Se l'operazione è mwfacommutativa si parla di mwfqsemigruppo commutativo o mwfgsemigruppo abeliano.

• Primi esempi

• Semigruppi e monoidi

• Altri esempi di semigruppi

• Isomorfismi, sottosemigruppi e ideali

• Generazione di sottosemigruppi

• Semigruppi e gruppi

• Semigruppi di endofunzioni

• Bibliografia

• Voci correlate

• Altri progetti

• Collegamenti esterni

Si incontrano molti esempi di semigruppi, finiti e infiniti. Consideriamone alcuni facilmente definibili.

• L'insieme vuoto.

• L'insieme dei numeri interi positivi munito dell'addizione (operazione notoriamente associativa). Questo semigruppo è commutativo.

• L'insieme dei numeri interi naturali munito della moltiplicazione (anche questa operazione è notoriamente associativa). Questo semigruppo è commutativo.

• L'insieme mwhw { 1 , 2 , 3 , 4 } {\displaystyle \{1,2,3,4\}} munito dell'operazione mwia max ( m , n ) {\displaystyle \max(m,n)} : per l'associatività basta osservare che, evidentemente,

mwiwmwjamwjq max ( max ( m , n ) , p ) = max ( m , n , p ) = max ( m , max ( n , p ) ) . {\displaystyle \max(\max(m,n),p)=\max(m,n,p)=\max(m,\max(n,p)).}

Questo semigruppo è commutativo ed è un semigruppo finito di 4 elementi. La sua tavola di moltiplicazione consiste nella matrice

mwkgmwkwmwla [ 1 2 3 4 2 2 3 4 3 3 3 4 4 4 4 4 ] . {\displaystyle {\begin{bmatrix}1&2&3&4\\2&2&3&4\\3&3&3&4\\4&4&4&4\end{bmatrix}}.}

• L'insieme di tutte le mwlwendofunzioni definite su un insieme mwma S , {\displaystyle S,} ad esempio su mwmq { 1 , 2 , 3 , 4 } {\displaystyle \{1,2,3,4\}} , munito della composizione di funzioni. La mwmgcomposizione di funzioni è infatti associativa. Questo semigruppo non è commutativo. In effetti non è commutativo neppure il semigruppo delle endofunzioni di un qualsiasi insieme ambiente mwmw S {\displaystyle S} formato da 2 o più elementi. Per questo basta considerare il controesempio di due endofunzioni che non commutano: se mwna a {\displaystyle a} e mwnq b {\displaystyle b} sono due elementi diversi di mwng S , {\displaystyle S,} introduciamo le due funzioni a valore costante mwnw f a {\displaystyle f_{a}} e mwoa f b {\displaystyle f_{b}} , definite da mwoq f a ( s ) = a {\displaystyle f_{a}(s)=a} e mwog f b ( s ) = b {\displaystyle f_{b}(s)=b} per ogni mwow s ∈ ∈ S . {\displaystyle s\in S.} Le due composizioni di queste funzioni danno quindi

mwpgmwpwmwqa ( f a ∘ ∘ f b ) ( s ) = a ≠ ≠ b = ( f b ∘ ∘ f a ) ( s ) , per ogni s ∈ ∈ S , {\displaystyle (f_{a}\circ f_{b})(s)=a\neq b=(f_{b}\circ f_{a})(s),\qquad {\text{per ogni }}s\in S,}

da cui risulta che mwqw f a ∘ ∘ f b ≠ ≠ f b ∘ ∘ f a . {\displaystyle f_{a}\circ f_{b}\neq f_{b}\circ f_{a}.}

• L'insieme, numerabile, di tutte le mwrgstringhe sopra un dato alfabeto munito della giustapposizione di stringhe. La giustapposizione di stringhe è una specie di archetipo delle operazioni binarie associative. Questo semigruppo si chiama semigruppo libero sull'alfabeto prefissato. Questo semigruppo non è commutativo se viene costruito su un alfabeto di due o più caratteri.

Un mwtamonoide, chiamato anche mwtqsemigruppo unitale o mwtgunitario, è un semigruppo dotato di un mwtwelemento neutro. Ad ogni semigruppo mwua S {\displaystyle S} non dotato di elemento neutro diventa un monoide aggiungendo un elemento neutro mwuq e {\displaystyle e} non facente parte di mwug S {\displaystyle S} tale che mwuw e s = s = s e {\displaystyle es=s=se} per ogni mwva s {\displaystyle s} in mwvq S {\displaystyle S} e mwvg e e = e {\displaystyle ee=e} . Un tale ampliamento può essere effettuato più volte (i "vecchi" elementi neutri non sono più tali, ma assorbono la composizione con i "nuovi").

Togliendo al monoide l'elemento neutro (o, in caso, gli elementi neutri,) si ottiene un semigruppo senza elementi neitro. Vanno rimosse anche le unità e riga e colonna corrispondenti della tavola di moltiplicazione; questo semigruppo potrebbe contenere o non contenere un nuovo elemento neutro. Dunquee

Lo studio dei monoidi aggiunge ben poco allo studio dei semigruppi: le due specie di strutture sono sostanzialmente equivalenti.

Un monoide con base si definisce mwwwmonoide libero: esso è un semigruppo con elemento neutro dotato di base per i suoi elementi. Il linguaggio di un mwxaautoma a stati finiti rappresentato dall'insieme delle stringhe su un certo alfabeto mwxq Σ Σ {\displaystyle \Sigma } è un esempio importante di monoide libero.

• Ogni mwyqgruppo può considerarsi un monoide.

• Ogni mwywideale di un qualsiasi mwzaanello, munito dell'operazione di moltiplicazione per l'anello.

• Ogni mwzgsottoinsieme di un semigruppo che sia chiuso per l'operazione di semigruppo.

• Un semigruppo la cui operazione è mwaacommutativa e mwaqidempotente è un mwagsemireticolo. Semireticoli di questo genere sono dati dalla collezione dei sottoinsiemi di un dato ambiente munita dell'intersezione (oppure dell'unione).

• L'insieme di tutte le relazioni entro un insieme munito della composizione tra relazioni.

• L'insieme di tutti i linguaggi su un dato alfabeto munito della giustapposizione fra linguaggi.

Introduciamo ora le relazioni e le costruzioni che costituiscono il normale armamentario per lo studio delle caratteristiche delle strutture algebriche della specie semigruppi. Per brevità, l'operazione del semigruppo generico viene presentata con la semplice giustapposizione, cioè mwbwxy denota il risultato della applicazione dell'operazione di semigruppo alla mwcacoppia ordinata (mwcqx, mwcgy). Se mwcwA e mwdaB sono sottoinsiemi di un semigruppo, allora mwdqAB denota l'insieme { mwdgab | mwdwa in mweaA e mweqb in mwegB }.

Due semigruppi mwfaS e mwfqT si dicono mwfgisomorfi se esiste una mwfwbiiezione mwgafmwgq : mwggS → mwgwT con la proprietà che, per ogni coppia di elementi mwhaa, mwhqb in mwhgS, mwhwf(mwiaab) = mwiqf(mwiga)mwiwf(mwjab). In questo caso mwjqf si dice mwjgisomorfismo di mwjwS su mwkaT. Se ci si limita a considerare le caratteristiche degli elementi dei semigruppi collegate alle operazioni di tali strutture due semigruppi isomorfi sono del tutto equivalenti: potranno invece essere distinti da altre proprietà derivanti dalle modalità secondo le quali sono stati costruiti.

Un sottoinsieme mwkgA non vuoto di un semigruppo mwkwS viene detto mwlasottosemigruppo di mwlqS se è chiuso per la operazione di semigruppo, ossia se mwlgAA è un sottoinsieme di mwlwA. mwmaA viene detto mwmqideale destro se mwmgAS è sottoinsieme di mwmwA, e simmetricamente viene chiamato mwnaideale sinistro se mwnqSA è sottoinsieme di mwngA. Se mwnwA è contemporaneamente ideale sinistro e ideale destro, allora viene chiamato mwoaideale bilatero o semplicemente mwoqideale di mwogS. Si vede rapidamente che l'intersezione di due ideali è anch'essa un ideale: se ne deduce che un semigruppo può avere al più un ideale minimale. Il generico ideale del semigruppo degli interi positivi muniti dell'addizione è l'insieme dei multipli di un qualsiasi intero positivo. Si vede quindi che il semigruppo additivo dei positivi non possiede ideale minimale. L'ideale minimale di un semigruppo commutativo, quando esiste, è un gruppo.

Se mwpgS è un semigruppo, allora l'intersezione di ogni collezione di suoi sottosemigruppi è anch'essa un sottosemigruppo si mwpwS. Dunque i sottosemigruppi di mwqaS formano un mwqqreticolo completo. Per ogni sottoinsieme mwqgA di mwqwS tra i sottosemigruppi di mwraS che contengono tale mwrqA ne esiste uno ed uno solo minimale per la inclusione; se lo denotiamo mwrwT, si dice che mwsaA mwsqgenera mwsgT. Ogni elemento mwswx di mwtaS genera il sottosemigruppo { mwtqxmwtgmwtwn |: mwuan intero positivo } che si denota <mwuqx>. Se tale sottoinsieme di mwugS è finito si dice che mwuwx è di mwvaordine finito, oppure che ha ordine finito; più precisamente si dice mwvqordine di mwvgx in mwvwS la mwwacardinalità del sottosemigruppo generato. Se viceversa <mwwqx> è infinito (evidentemente infinito numerabile) si dice che mwwgx è di, oppure ha, mwwwordine infinito.

Si dice mwxqsemigruppo periodico ogni semigruppo costituito solo da elementi di ordine finito. Chiaramente ogni semigruppo finito è periodico.

Si dice mwxwsemigruppo monogenico ogni semigruppo che può considerarsi generato da un singolo elemento (talora viene detto anche mwyasemigruppo ciclico, ma questa espressione può indurre confusione). Ogni semigruppo monogenico infinito è isomorfo al semigruppo additivo degli interi positivi.

Anche i semigruppi monogenici finiti possono essere individuati in modo esauriente. Denotando mwygx un suo generatore e mwywn la sua cardinalità i suoi elementi possono essere elencati come successive potenze di mwzax: mwzqx, mwzgxmwzw2, ... ,mw0axmw0qn; la successiva potenza mw0gxmw0wn+1 deve coincidere con una potenza inferiore, scriviamola mw1axmw1qk. Gli interi mw1gn e mw1wk caratterizzano completamente il semigruppo. Consideriamo l'insieme di p:=n-k+1 elementi Gmw2a := {m=k, k+1, ...,nmw2q :| mw2gxmw2wm }. Chiaramente esso costituisce un sottosemigruppo di mw3aS; più precisamente si tratta di un gruppo, in quanto i suoi elementi vengono permutati quando vengono moltiplicati per uno di essi. Se mw3qk=1 il semigruppo è il mw3ggruppo ciclico di mw3wn elementi. L'unità del sottogruppo è un idempotente del semigruppo; ogni altro elemento del semigruppo moltiplicato per sé stesso porta ad un altro elemento. Dunque ogni semigruppo periodico finito contiene almeno un elemento idempotente e ogni semigruppo monogenico finito contiene esattamente un idempotente. Si osserva anche che il sottogruppo (gruppo ciclico) di un semigruppo monogenico finito è un ideale del semigruppo.

Un sottosemigruppo di un semigruppo mw4gS che è anche un gruppo viene detto mw4wmw5asottogruppo di mw5qS. Vi è una stretta relazione tra i sottogruppi di un semigruppo e i suoi idempotenti. Ogni sottogruppo contiene esattamente un idempotente, cioè l'elemento neutro del semigruppo. Per ogni idempotente mw5ge del semigruppo esiste un unico sottogruppo massimale che contiene mw5we. Ogni sottogruppo massimale viene individuato in questo modo, e di conseguenza esiste una corrispondenza biunivoca tra idempotenti e sottogruppi massimali. Si dovrebbe notare che il termine mw6asottogruppo massimale viene qui usato in modo differente da come viene usato in teoria dei gruppi. In questa teoria un sottogruppo massimale si sottintende che sia un sottogruppo proprio. Quando è considerato come semigruppo, un gruppo possiede solo un sottogruppo massimale, cioè sé stesso.

Ogni semigruppo può considerarsi un semigruppo di endofunzioni: infatti si può associare ad ogni elemento mw6wy di un semigruppo mw7aS la endofunzione di mw7qS corrispondente alla moltiplicazione a destra per mw7gy dei suoi varielementi. Viceversa ad ogni insieme mw7wE di endofunzioni di un insieme ambiente mw8aA si associa il semigruppo <mw8qE> generato dagli elementi di mw8gE (e da tutti i loro prodotti). Se mw8wA è infinito il semigruppo <mw9aE> può essere finito o infinito; se mw9qA è finito <mw9gE> evidentemente deve essere finito.

Si possono considerare anche semigruppi generati da insiemi di relazioni entro un insieme ambiente. Si trova che questi semigruppi si possono ridurre a semigruppi di endofunzioni: si tratta di passare dalle relazioni entro un insieme mw-aA alle endofunzioni entro l'insieme delle parti di mw-qA. I semigruppi di endofunzioni entro insiemi finiti possono essere convenientemente trattati come semiautomi deterministici (a stati finiti), mentre i semigruppi di relazioni entro insiemi finiti possono essere trattati come semiautomi non-deterministici. In proposito si veda teoria degli automi a stati finiti.

I risultati su questi semigruppi e questi automi possono essere formulati anche come fatti riguardanti relazioni di congruenza entro monoidi liberi su alfabeti finiti che forniscono quozienti finiti. In proposito si veda teoria dei linguaggi razionali (o dei linguaggi regolari).

Sui semigruppi finiti visti nei modi precedenti si può dire molto di più. Notevoli risultati sulla classificazione delle strutture di tali semigruppi finiti sono ottenuti dalla teoria di Krohn-Rhodes.

• mwaqq(EN) John M. Howie (1995): mwaquFundamentals of Semigroup Theory, Oxford University Press, ISBN 0198511949

• mwaqg(EN) mwaqkAldo Belleni Morante, mwaqoApplied semigroups and evolution equations, Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York, 1979. XV+387 pp. ISBN 0-19-853529-5

• mwaq0(EN) Aldo Belleni Morante, mwaq4A Concise Guide to Semigroups and Evolution Equations, Series on Advances in Mathematics for Applied Sciences, World Scientific Publishing Co. Inc., River Edge, NJ, 1994. XIV+164 pp. ISBN 981-02-1294-1

• mwarmGruppo (matematica)

• mwaruGruppo di Grothendieck

• mwarcLinguaggio formale

Altri progetti

• Wikizionario

• Wikizionario contiene il lemma di dizionario «semigruppo»

• citereftreccani-itSemigruppo, su Treccani.it – Enciclopedie on line, Istituto dell'Enciclopedia Italiana.

• citerefdizionario-delle-scienze-fisicheSemigruppo, in Dizionario delle scienze fisiche, Istituto dell'Enciclopedia Italiana, 1996.

• citerefvocabolario-treccaniSemigruppo, su Vocabolario Treccani, Istituto dell'Enciclopedia Italiana.

• citerefsapere-itsemigrùppo, su sapere.it, De Agostini.

• citerefenciclopedia-della-matematicaSemigruppo, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.

• citerefbritannica-com(EN) semigroup, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.

• citerefmathworld(EN) Eric W. Weisstein, Semigroup, su MathWorld, Wolfram Research.

• citerefspringereom(EN) Semi-group, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.